Codeforces Round #86 (Div. 2)

A

弱智题，不断用 $l$ 除以 $k$ 即可。

#include <cstdio>

int k, l, cnt;

int main() {
    scanf("%d%d", &k, &l);
    while (l % k == 0) cnt++, l /= k;
    if (l == 1) printf("YES\n%d\n", cnt - 1);
    else puts("NO");
}

B

看到数据范围 $n\le 16$ 考虑状压，直接暴力枚举子集判断是否有冲突即可。

时间复杂度 $O(n^22^n)$ 。

Code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 20;

string s[N], a, b;
int f[N][N], n, m, ans;

int find(string str) {
    int i = 0;
    while (str != s[i]) i++;
    return i;
}

int popcount(int x) {
    int ret = 0;
    while (x) ret += x & 1, x >>= 1;
    return ret;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i <= n - 1; i++) cin >> s[i];
    sort(s, s + n);
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        int u = find(a), v = find(b);
        f[u][v] = f[v][u] = 1;
    }
    for (int s = 0; s <= (1 << n) - 1; s++) {
        int flag = 0;
        for (int i = 0; i <= n - 1; i++) {
            if ((s >> i & 1) == 0) 
                continue;
            for (int j = i + 1; j <= n - 1; j++) {
                if ((s >> j & 1) == 0) 
                    continue;
                flag |= f[i][j];
                if (flag) break;
            }
            if (flag) break;
        }
        if (flag == 0) {
            if (popcount(s) > popcount(ans))
                ans = s;
        }
    }
    cout << popcount(ans) << endl;
    for (int i = 0; i <= n - 1; i++) {
        if (ans >> i & 1)
            cout << s[i] << endl;
    }
}

C

大模拟，不知道为什么死活写不对。

搬一个题解代码。

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;

const int N = 1e5 + 5;

char s[N], word[N];
int type[N], tp, p, flag, cnt, len, t;

int modify() {
    int l = strlen(word);
    if (l < 3) return 0;
    if (strcmp(word + l - 4, "lios") == 0) return 1;
    if (strcmp(word + l - 5, "liala") == 0) return -1;
    if (strcmp(word + l - 3, "etr") == 0) return 2;
    if (strcmp(word + l - 4, "etra") == 0) return -2;
    if (strcmp(word + l - 6, "initis") == 0) return 3;
    if (strcmp(word + l - 6, "inites") == 0) return -3;
    return 0;
}

int main() {
    cin.getline(s, N);
    flag = 1;
    len = strlen(s);
    for (int i = 0; i <= len; i++) {
        if (s[i] != ' ' && s[i] != '\0')
            word[p++] = s[i];
        else {
            word[p] = '\0';
            cnt++;
            t = modify();
            if (t != 0) type[tp++] = t;
            else {
                flag = 0;
                break;
            }
        }
    }
    if (cnt == 1 && flag == 1) {
        puts("YES");
        return 0;
    }
    if (flag == 0) {
        puts("NO");
        return 0;
    }
    cnt = 0;
    for (int i = 0; i < tp; i++) {
        if (abs(type[i]) == 2)
            cnt++;
    }
    if (cnt != 1) {
        puts("NO");
        return 0;
    }
    flag = 1;
    if (type[0] < 0) {
        for (int i = 1; i < tp; i++)
            if (type[i] > 0) {
                flag = 0;
                break;
            }
    }
    else {
        for (int i = 1; i < tp; i++)
            if (type[i] < 0) {
                flag = 0;
                break;
            }
    }
    if (flag == 0) {
        puts("NO");
        return 0;
    }
    flag = 1;
    for (int i = 1; i < tp; i++) {
        if (abs(type[i]) < abs(type[i - 1])) {
            flag = 0;
            break;
        }
    }
    if (flag) puts("YES");
    else puts("NO");
}
<!-- more -->

D

考虑字符串哈希。找出 $S_{begin}$ 和 $S_{end}$ 在 $T$ 中出现的位置，暴力枚举端点，对哈希值去重即可。

时间复杂度 $O(n^2\log{n})$ 。

#include <cstdio>
#include <cstring>
#include <vector>
#include <unordered_set>

const int N = 2005;
const int base = 131;

char be[N], ed[N], s[N];
std::vector<int> p, q;

typedef unsigned long long uint64;

uint64 hash[N], Pow[N], f, g;
std::unordered_set<uint64> st;

uint64 getHash(int x, int l) {
    return hash[x] - hash[x + l] * Pow[l];
}

int main() {
    scanf("%s%s%s", s, be, ed);
    int n = strlen(s);
    int m = strlen(be);
    int k = strlen(ed);
    Pow[0] = 1;
    for (int i = 1; i < N; i++) Pow[i] = Pow[i - 1] * base;
    hash[n] = 0;
    for (int i = n - 1; i >= 0; i--) hash[i] = hash[i + 1] * base + s[i];
    for (int i = m - 1; i >= 0; i--) f = f * base + be[i];
    for (int i = k - 1; i >= 0; i--) g = g * base + ed[i];
    for (int i = 0; i + m <= n; i++) {
        if (getHash(i, m) == f) 
            p.push_back(i);
    }
    for (int i = 0; i + k <= n; i++) {
        if (getHash(i, k) == g)
            q.push_back(i + k - 1);
    }
    int ans = 0;
    for (int i: p) for (int j: q) {
        int l = j - i + 1;
        if (i <= j && l >= std::max(m, k)) {
            uint64 val = getHash(i, l);
            if (!st.count(val)) ans++, st.insert(val);
        }
    }
    printf("%d\n", ans);
}

E

注意到

$x=s^2+t^2,s,t\in\mathbb{Z}\Longleftrightarrow x=2k+1\vee x=4k,\,k\in\mathbb{Z}$

所以只需判断素数是否模 $4$ 余 $1$ 。

由于CF的测评机跑得特别快可以暴力筛出 $3\times 10^8$ 以内的所有素数，依次枚举即可。

注意数组开不下，需要使用 bitset。

时间复杂度 $O(n)$ 。

Code

#include <iostream>
#include <cstdio>
#include <bitset>

const int N = 3e8 + 5;
const int M = 2e7 + 5;

std::bitset<N> vis;
int prime[M], l, r, cnt, ans;

inline void sieve() {
	for (int i = 2; i <= r; i++) {
		if (!vis[i]) prime[++cnt] = i;
		for (int j = 1; j <= cnt && i * prime[j] <= r; j++) {
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}

int main() {
	scanf("%d%d", &l, &r);
	sieve();
	for (int i = 1; i <= cnt; i++) {
		if (prime[i] < l) continue;
		if (prime[i] % 4 == 1) ans++;
	}
	printf("%d\n", ans + (l <= 2 && r >= 2));
	return 0;
}